package com.liang.leetcode.dp;

/**
 * 746.使用最小花费爬楼梯
 */
public class Dp03_MinCostClimbingStairs {
    public static void main(String[] args) {
        int[] cost = {10, 15, 20};
        System.out.println(minCostClimbingStairs(cost));
    }

    /**
     * cost[i] 表示从第 i 层台阶往上爬一个或两个台阶所需要花费的体力
     */
    public static int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        // dp[i] 表示到达第i台阶所花费的最少体力
        int[] dp = new int[n + 1];
        // 到达第0个台阶不花费体力，从第0个台阶往上跳需要花费cost[0]的体力
        dp[0] = 0;
        dp[1] = 0;
        // 从第 2 层台阶往上爬开始遍历
        for (int i = 2; i <= n; i++) {
            // dp[i-1] 表示前面跳到 i-1 阶台阶花费的体力，cost[i-1] 表示当前跳到 i-1 台阶的体力花费
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}
